package LeetCode.month01.day18;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;

public class No32 {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses("(()"));
    }
    public static int longestValidParentheses(String s) {
        //贪心思想
        int maxans = 0;
        int left =0,right=0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if(s.charAt(i)=='('){
                left++;
            }else{
                right++;
            }
            if(left==right){
                maxans = Math.max(maxans,2*right);
            }else if(right>left){
                left = right = 0;
            }
        }
        left=right=0;
        for (int i = len-1; i >= 0; i--) {
            if(s.charAt(i)=='('){
                left++;
            }else{
                right++;
            }
            if(left==right){
                maxans = Math.max(maxans,2*left);
            }else if(left>right){
                left = right = 0;
            }
        }
        return maxans;




        //栈
//        Deque<Integer> deque = new LinkedList<>();
//        int maxans = 0;
//        deque.push(-1);
//        int len = s.length();
//        for (int i = 0; i < len; i++) {
//            if(s.charAt(i)=='(') deque.push(i);
//            else{
//                deque.pop();
//                if(deque.isEmpty()){
//                   deque.push(i);
//                }else{
//                    maxans = Math.max(maxans,i-deque.peek());
//                }
//            }
//        }
//        return maxans;




        //动态规划
//        int maxans = 0;
//        int len = s.length();
//        int[] dp = new int[len];
//        for (int i = 1; i < len; i++) {
//            if(s.charAt(i)==')'){
//                if(s.charAt(i-1)=='('){
//                    dp[i]=(i>=2?dp[i-2]:0)+2;
//                }else if(i-dp[i-1]>0&&s.charAt(i-dp[i-1]-1)=='('){
//                    dp[i]= dp[i-1]+((i-dp[i-1])>2?dp[i-dp[i-1]-2]:0)+2;
//                }
//            }
//            maxans = Math.max(dp[i],maxans);
//        }
//        System.out.println(Arrays.toString(s.toCharArray()));
//        System.out.println(Arrays.toString(dp));
//        return maxans;
    }
}
